#ifdef a
//top-k问题
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>

//Swap
void Swap(int* left, int* right) {
	int temp = *left;
	*left = *right;
	*right = temp;
	return;
}

//向下调整
void AdjustDown(int* arr, int parent, int size) {
	int child = (2 * parent) / 2;
	while (child < size) {
		if (child + 1 < size && arr[child] > arr[child + 1])
			child += 1;
		if (arr[child] < arr[parent]) {
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = (2 * parent) / 2;
		}
		else {
			return;
		}
	}
	return;
}

//Top_K（前 k 个最大的元素->降序->小堆）
void Top_K(int* arr, int numSize, int k) {
	//建小堆
	for (int i = (k - 2) / 2; i >= 0; i--) {
		AdjustDown(arr, i, k);
	}
	//比较
	for (int i = k; i < numSize; i++) {
		if (arr[i] > arr[0]) {
			Swap(&arr[i], &arr[0]);
			AdjustDown(arr, 0, k);
		}
	}
	//堆排序
	int end = k - 1;
	while (end) {
		Swap(&arr[end], &arr[0]);
		AdjustDown(arr, 0, end);
		end--;
	}
	return;
}

//打印
void RetPrint(int arr[], int k) {
	for (int i = 0; i < k; i++)
		printf("%d ", arr[i]);
	printf("\n");
	return;
}
int main() {
	srand((unsigned int)time(NULL));
	int size = 10000;
	int* arr = (int*)malloc(sizeof(int) * size);
	if (!arr) {
		assert(0);
		return;
	}
	int k;
	scanf("%d", &k);
	for (int i = 0; i < size; i++) {
		arr[i] = rand() % 10000;
	}
	arr[0] = 10000 + 1;
	arr[2] = 10000 + 2;
	arr[3] = 10000 + 3;
	arr[4] = 10000 + 4;
	arr[5] = 10000 + 5;
	arr[6] = 10000 + 6;
	arr[7] = 10000 + 7;
	arr[8] = 10000 + 8;
	arr[9] = 10000 + 9;
	arr[10] = 10000 + 10;
	Top_K(arr, size, k);
	RetPrint(arr, k);
	return 0;
}
#endif

